#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
typedef int SLTDataType;//以存放整型数据为例
typedef struct SListNode
{
SLTDataType data;//数据域：用于存储该结点的数据
struct SListNode* next;//指针域：用于存放下一个结点的地址
}SListNode;

//打印链表
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;//接收头指针
  while (cur != NULL)//判断链表是否打印完毕
  {
    printf("%d->", cur->data);//打印数据
    cur = cur->next;//指针指向下一个结点
  }
  printf("NULL\n");//打印NULL，表明链表最后一个结点指向NULL
}

//增加节点
SListNode* BuySLNode(SLTDataType x)
{
  SListNode* node = (SListNode*)malloc(sizeof(SListNode));
  if(node==NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }

  node->data = x;
  node->next = NULL;
  return node;
}

//头插
void SListPushFront(SListNode** pplist,SLTDataType x)
{
  SListNode* newnode = BuySLNode(x);
  newnode->next = *pplist;
  *pplist = newnode;//改变了头节点，二级指针
}

//尾插
void SListPushBack(SListNode** pplist,SLTDataType x)
{
  SListNode* newnode;
  newnode = BuySLNode(x);
  if(*pplist==NULL)
  {
    *pplist= newnode;
  }

  else 
  {
    SListNode* tail = *pplist;
    while(tail->next!=NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

//查找数据
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;//接收头指针
while (cur != NULL)//遍历链表
{
if (cur->data == x)//判断结点是否为待找结点
return cur;//返回目标结点的地址
cur = cur->next;//指针后移
}
return NULL;//没有找到数据为x的结点
}
//给定位置之前插入
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x)
{
  assert(pos);//确保传入地址不为空
  SListNode* newnode = BuySLNode(x);//申请一个新结点
  if (pos == *pplist)//判断给定位置是否为头指针指向的位置
  {
    newnode->next = pos;//让新结点的指针域指向地址为pos的结点
    *pplist = newnode;//让头指针指向新结点
  }
  else
  {
    SListNode* prev = *pplist;//接收头指针
    while (prev->next != pos)//找到地址为pos的结点的前一个结点
    {
      prev = prev->next;
    }
    newnode->next = prev->next;//让新结点的指针域指向地址为pos的
    prev->next = newnode;//让前一个结点指向新结点
  }
}
//尾删
void SListPopBack(SListNode** pplist)
{
  if(*pplist==NULL)
  {
    return ;
  }

  else if((*pplist)->next ==NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }

  else 
  {
    SListNode* prev = *pplist;
    SListNode* cur = (*pplist)->next;
    while(cur->next!=NULL)
    {
      prev = cur;
      cur = cur->next;
    }
    free(cur);
    cur = NULL;
    prev->next = NULL;
  }

}
int main()
{
  SListNode* List = NULL;
 // SListPushFront(&List,7);
  SListPushBack(&List,3);
  SListPushBack(&List,4);
  SListPushFront(&List,2);
  SListInsertBefore(&List,SListFind(List,2),1);
  SListPopBack(&List);
  SListPrint(List);
  return 0;
}




